package problem76;

//76.最小覆盖子串
//https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        int[] hash1 = new int[127];
        int[] hash2 = new int[127];
        int size = 0;
        for(char ch : t.toCharArray()) {
            if(hash1[ch] == 0) size++;
            hash1[ch]++;
        }

        int index = -1, minLen = Integer.MAX_VALUE;
        int count = 0;
        for(int i = 0, j = 0; j<n; j++) {
            char ch = s.charAt(j);
            hash2[ch]++;
            if(hash2[ch] == hash1[ch]) count++;
            while(count == size) {
                if(j-i+1 < minLen) {
                    minLen = j-i+1;
                    index = i;
                }
                if(hash1[s.charAt(i)] == hash2[s.charAt(i)]) count--;
                hash2[s.charAt(i)]--;
                i++;
            }
        }
        if(index == -1) return "";
        else return s.substring(index, index + minLen);
    }
}